#include <iostream>
#include <vector>
#include <stack>
using namespace std;

// 找到左侧最近的大于自己的数
const vector<int> LeftBigerNum(const vector<int> &par)
{
    stack<int> st;
    vector<int> res(par.size());
    for (int i = 0; i < par.size(); i++)
    {
        // 找到比自己大的
        while (st.size() && par[st.top()] < par[i])
            st.pop();
        // 如果栈中没有那么，结果数组就是0
        if (st.size() == 0)
        {
            res[i] = 0;
        }
        else
        {
            res[i] = par[st.top()]; // 如果找到了，那么赋值结果数组
        }
        st.push(i); // 都要把自己放进去
    }
    return res;
}
// 找到右侧距离自己最近的且比自己小的
const vector<int> RightBigerNum(const vector<int> &par)
{
    stack<int> st;
    vector<int> res(par.size());
    for (int i = par.size() - 1; i >= 0; i--)
    {
        while (st.size() && par[st.top()] < par[i])
            st.pop();
        if (st.empty())
        {
            res[i] = 0;
        }
        else
        {
            res[i] = par[st.top()];
        }
        st.push(i); // 把自己放进去
    }
    return res;
}

const vector<int> LeftSmallerNum(const vector<int> &par)
{
    stack<int> st;
    vector<int> res(par.size());
    for (int i = 0; i < par.size(); i++)
    {
        while (st.size() && par[st.top()] > par[i])
            st.pop();
        if (st.empty())
        {
            res[i] = 0;
        }
        else
        {
            res[i] = par[st.top()];
        }
        st.push(i);
    }
    return res;
}

const vector<int> RightSmallerNum(const vector<int> &par)
{
    stack<int> st;
    vector<int> res(par.size());
    for (int i = par.size()-1; i >=0 ; i--)
    {
        while (st.size() && par[st.top()] > par[i])
            st.pop();
        if (st.empty())
        {
            res[i] = 0;
        }
        else
        {
            res[i] = par[st.top()];
        }
        st.push(i);
    }
    return res;
}

static void debug(const vector<int> &args)
{
    for (const auto &x : args)
        cout << x << " ";
    cout << endl;
}

int main()
{

    vector<int> nums{5, 4, 1, 2, 6, 7};
    cout<<"原数组: ";
    debug(nums);
    // 找出左侧最大的数

    auto ret1 = LeftBigerNum(nums);
    auto ret2 = RightBigerNum(nums);
    auto ret3 = LeftSmallerNum(nums);
    auto ret4 = RightSmallerNum(nums);
    cout<<"找到左侧最近的大于自己的数: ";
    debug(ret1);
    cout<<"找到右侧最近的大于自己的数: ";
    debug(ret2);
    cout<<"找到左侧最近的小于自己的数: ";
    debug(ret3);
    cout<<"找到右侧最近的小于自己的数: ";
    debug(ret4);
    return 0;
}